<?php
namespace core\test;
/**
 * 排序书算法
 */
class Sort{
    
    /**
     * 冒泡排序
     */
    public static function bubbleSort($list){
        //$list = [ 1,3,5,7,9,2,4,6,8]; 
        $len = count( $list );
        $count = 0;
        for( $i = 0; $i < $len - 1; $i++ ){
            for( $j =0 ; $j< $len - 1 - $i; $j++ ){
                //dump('aa_'.$i.'_'.$j);
                //$count ++;
                if( $list[$j] > $list[$j+1] ){
                    $temp = $list[$j+1];
                    $list[$j+1] = $list[$j];
                    $list[$j]   = $temp;
                }
            }
        }        
        //dump($count);
        return $list;
    }
    
    /**
     * 选择排序
     */
    public static function selectionSort($list){
        $len = count( $list );
        //$count = 0;
        for( $i = 0; $i < $len -1 ; $i ++ ){
            $minIndex = $i;
            for( $j = $i + 1; $j < $len ; $j ++){
                $count++;
                if( $list[$j] < $list[$minIndex] ){
                    $minIndex = $j;
                }
            }
            $temp = $list[$i];
            $list[$i] = $list[$minIndex];
            $list[$minIndex] = $temp;
        }
        //dump($count);
        return $list;
    }
    
    /**
     * 插入排序
     */
    public static function insertionSort($list){
        $len = count( $list);
        $count = 0;
        for($i = 1; $i < $len ; $i ++){
            $preIndex = $i -1;
            $current  = $list[$i];
            while( $preIndex >= 0 && $list[$preIndex] > $current ){
                $list[$preIndex+1] = $list[$preIndex];
                $preIndex --;
            }
            $list[$preIndex+1] = $current;
        }
        return $list;
    }
    
    /**
     * 希尔排序
     */
    public static function shellSort($list){
        $count = 0;
        $len = count( $list );
        $gap = 1; $temp;
        while( $gap < $len / 3 ){
            $gap = $gap * 3 +1;
        }
        for( $gap ; $gap > 0 ; $gap = floor( $gap / 3)){
            for( $i = $gap ; $i < $len ; $i ++ ){
                $temp = $list[$i];
                for( $j = $i - $gap ; $j > 0 && $list[$j] > $temp ; $j-=$gap){
                    $list[$j+ $gap] = $list[$j];
                }
                $list[$j+ $gap] = $temp;
            }
        }
        return $list;
        
    }
    
    
    
}